package com.practice.list;

import java.util.Arrays;

public class CyclicList {
	private	Node		root;
	
	public void insert(Node node, int value) {
		Node current = node;
		Node next = node.next;
		Node newNode = new Node(value);

		while (next != node) {	// case 3
			// case 1
			if (current.value <= value && value <= next.value) break;
			
			// case 2
			if (current.value > next.value && 
					(value >= current.value || value <= next.value)) break;
			
			current = next;
			next = next.next;
		}
		
		newNode.next = current.next;
		current.next = newNode;
	}
	
	public void print() {
		int v = root.value;
		Node node = root.next;
		System.out.print(v);
		
		while (node.value != v) {
			System.out.print(" " + node.value);
			node = node.next;
		}
		System.out.println();
	}
	
	public Node get(int index) {
		Node node = root;
		for (int i=0; i<index; i++) {
			node = node.next;
		}
		return node;
	}
	
	public boolean assertOrder() {
		Node current = root;
		Node next = current.next;
		while (current.value <= next.value && next!=root) {
			current = next;
			next = next.next;
		}
		
		if (next == root) return true;
		current = next;
		while (current!=root) {
			if (current.value > current.next.value) return false;
			current = current.next;
		}
		
		return true;
	}
	
	public void createList(int[] a) {
		Arrays.sort(a);
		root = new Node(a[0]);
		Node prev = root;
		for (int i=1; i<a.length; i++) {
			Node node = new Node(a[i]);
			prev.next = node;
			prev = node;
		}
		prev.next = root;
	}
	
	private class Node {
		Node	next;
		int		value;
		public Node(int value) {
			this.value = value;
		}
	}
}
